#include <stdio.h>
#include <gmp.h>

// 二分幂算法（GMP高精度版，修复参数错误）
void binary_exponentiation(mpz_t result, const mpz_t base, unsigned long power) {
    mpz_t power_2, p;
    mpz_inits(power_2, p, NULL);  // 初始化GMP变量

    mpz_set_ui(power_2, 1);       // power_2 = 1（2^0）
    mpz_set_ui(result, 1);        // 结果初始化为 1
    mpz_set(p, base);             // p = base（当前 base 的 2^k 次幂）

    // 循环条件：power_2 <= power（用GMP函数比较大整数和无符号整数）
    while (mpz_cmp_ui(power_2, power) <= 0) {
        // 修复：用 mpz_get_ui(power_2) 获取 power_2 的值，再和 power 做位运算
        if ((mpz_get_ui(power_2) & power) != 0) {
            mpz_mul(result, result, p);  // 高精度乘法：result = result * p
        }
        mpz_mul(p, p, p);                // p = p * p（平方更新）
        mpz_mul_ui(power_2, power_2, 2); // power_2 = power_2 * 2（等价于左移1位）
    }

    mpz_clears(power_2, p, NULL);  // 释放GMP变量
}

int main() {
    mpz_t base1, result1, expected1;
    mpz_t base2, result2, expected2;

    // 初始化GMP变量
    mpz_inits(base1, result1, expected1, base2, result2, expected2, NULL);

    // 测试用例1：3^100
    mpz_set_ui(base1, 3);
    binary_exponentiation(result1, base1, 100);
    mpz_pow_ui(expected1, base1, 100);  // GMP内置函数验证

    printf("3^100（自定义二分幂）: ");
    mpz_out_str(stdout, 10, result1);
    printf("\n3^100（GMP验证）:     ");
    mpz_out_str(stdout, 10, expected1);
    printf("\n是否相等: %s\n\n", mpz_cmp(result1, expected1) == 0 ? "是" : "否");

    // 测试用例2：32^15
    mpz_set_ui(base2, 32);
    binary_exponentiation(result2, base2, 15);
    mpz_pow_ui(expected2, base2, 15);  // GMP内置函数验证

    printf("32^15（自定义二分幂）: ");
    mpz_out_str(stdout, 10, result2);
    printf("\n32^15（GMP验证）:     ");
    mpz_out_str(stdout, 10, expected2);
    printf("\n是否相等: %s\n", mpz_cmp(result2, expected2) == 0 ? "是" : "否");

    // 释放GMP变量
    mpz_clears(base1, result1, expected1, base2, result2, expected2, NULL);
    return 0;
}